package temp.二叉树.层次遍历;

//给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
//
//
//
// 示例 1：
//
//
//输入：root = [3,9,20,null,null,15,7]
//输出：[[15,7],[9,20],[3]]
//
//
// 示例 2：
//
//
//输入：root = [1]
//输出：[[1]]
//
//
// 示例 3：
//
//
//输入：root = []
//输出：[]
//
//
//
//
// 提示：
//
//
// 树中节点数目在范围 [0, 2000] 内
// -1000 <= Node.val <= 1000
//
//
// Related Topics 树 广度优先搜索 二叉树 👍 673 👎 0

import temp.二叉树.TreeNode;

import java.util.*;

/**
 * 二叉树的层序遍历 II
 *
 * @author saint
 */
class P107_从底向上层次遍历 {
    public static void main(String[] args) {
        Solution solution = new P107_从底向上层次遍历().new Solution();

    }

    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if(root == null){
            return new ArrayList<>();
        }
        ArrayList<List<Integer>> ans = new ArrayList<>();
        //使用队列进行遍历
        Deque<TreeNode> queue = new LinkedList<>();
        queue.addLast(root);
        while(!queue.isEmpty()){
            int length = queue.size(); //本层结点个数
            ArrayList<Integer> tmp = new ArrayList<>();
            for (int i = 0; i < length; i++) {
                TreeNode now = queue.removeFirst();
                tmp.add(now.val);
                if(now.left!=null){
                    queue.addLast(now.left);
                }
                if (now.right!=null) {
                    queue.addLast(now.right);
                }
            }
            ans.add(tmp);
        }
        Collections.reverse(ans);
        return ans;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
